#!/usr/bin/env python
from ants import *
import random
import util
global debug
import time


# Various Globals
OTHER = {"n": ["e", "w", "s"],
         "e": ["n", "w", "s"],
         "s": ["n", "w", "e"],
         "w": ["n", "s", "e"]}
SIDES = {"n": ["e", "w"],
         "e": ["n", "s"],
         "s": ["w", "e"],
         "w": ["n", "s"]}

# edit this variable to customize where the debug
# output is piped to
debugFilePath = "C:\Users\Jim\Desktop\CS 3600\AI Challenge"


# used for debugging, writes out a data file to the
# path specified in debugFilePath with any piece
# of data passed in. It simply writes out the string
# representation of the parameter, and can take in
# multiple paramters, putting a tab between them.
# Either comment out everything but the return
# for submission/no debugging or comment out
# the return if you want debugging. This is a global
# function so using the debug(...) function call
# works everywhere in this file
def debug(*data):
##    return
    global debugFilePath
    import os
    temp = os.getcwd()
    os.chdir(debugFilePath)
    with open("data.txt", "a") as f:
        if len(data) > 1:
            for item in data:
                f.write(str(item))
                f.write("\t")
            f.write("\n")
        else:
            f.write(str(data[0]) + "\n")
            
    os.chdir(temp)

import os
temp = os.getcwd()
os.chdir(debugFilePath)
with open("data.txt", "w") as f: pass
os.chdir(temp)


class MyBot:
    groups = {}
    def __init__(self):
        # Used to create the specified group derived from pickGroup
        self.constructors = {"Explorer": Explorer, "Hunter": Hunter, "Buster": Buster }
        
    

    def do_setup(self, antInfo):
        self.antLocs = {}
        self.goals = {}
        self.groups = {"Explorer":[], "Hunter": [], "Buster":[]}
        self.map = antInfo.map
    

    def do_turn(self, ants):

        debug("TURN:", ants.turnNumber)

        # Because of respawning food, every 20 turns
        # the destination and path are reset for a group
        # so that the group will pursue food that appears
        # closer to them
        
        # TODO: UPDATE TO RESET SEQUENTIALLY INSTEAD OF RANDOMLY
##        for name in self.groups.keys():
##            groups = self.groups[name]
##            for group in groups:
##                if ((ants.turnNumber + group.id) % EXPLORER_GOAL_RESET) == 0:
##                    if group.destination != None:
##                        goals = [group.destination] + ants.food()
##                        x,y,path = self.aStar(group.location, goals, ants)
##                        if (x,y) != (group.destination[0], group.destination[1]):
##                            group.destination = (x,y)
##                        group.path = path
                    

        ourAnts = ants.my_ants()
        hills = ants.my_hills()
        dead = ants.my_dead_ants()
        enemyHills = ants.enemy_hills()

        debug(ourAnts)
        # updates our map with new water and enemy hills
        self.mergeMap(ants)
        for loc, owner in enemyHills:
            x,y = loc
            self.map[x][y] = "T"

        # Removes dead ants from their respective
        # groups via the antLocs hash map. This
        # is approximately O(n) with n being
        # the length of dead ants
        for ant in dead:
            group = self.antLocs.get( ant, None)
            if group != None and group != -1:
                group.removeAnt(ant)
                self.antLocs.pop(ant)

        # The logic for ant spawning. Because their
        # is a one turn delay for ant spawning EXCEPT
        # the first turn, a temp group is added so that
        # it takes one turn to respawn ants.
        for x,y in hills:

            # first turn logic, add all starting ants to
            # a new explorer group
            if ants.turnNumber == 1:
                group = Explorer([], ants, self)
                group.addAnt( (x,y) )
                self.antLocs[ (x,y) ] = group
                self.groups["Explorer"].append(group)
                self.map[x][y] = "M"

            # add a temp 1 turn delay group, -1
            elif self.antLocs.get( (x,y), None) == None and (x,y) in ourAnts:
                self.antLocs[ (x,y) ]= -1

            # actually add an ant to an existing group type if
            # there is one within range
            elif self.antLocs.get( (x,y), None) == -1:
                name, threshold = self.pickGroup()
                existing = self.groups[name]
                validGroup = None
                for group in existing:
                    dist = ants.distance(group.location, (x,y))
                    if dist <= 10 and len(group) < threshold:
                        if validGroup == None or (validGroup[1] > dist): validGroup = group, dist
                if validGroup == None:
                    group = self.constructors[name]([], ants, self)
                    self.groups[name].append(group)
                else:
                    group = validGroup[0]

                group.addAnt( (x,y) )
                self.antLocs[ (x,y) ] = group
        
                    

        debug("Number of Groups:", len(self.groups["Explorer"]))
        debug(self.antLocs)
        foodLocs = ants.food()

        # the turn logic, go through every group
        # and tell the group to move based on its logic
        for types in self.groups.keys():
            for group in self.groups[types]:
                group.move(foodLocs)
            
            if ants.time_remaining() < 10:
                debug("out of time trololo")
                break

    # decides which group that the ant should
    # be put into and how many ants can be
    # within a specific group

    # TODO: add logic to create more than the explorer group
    def pickGroup(self):
        return "Explorer", 2

    # If more than one group has the same destination,
    # then whenever this destination is reached we need
    # to remove the destination from the other groups
    def deleteGoals(self, loc):
        listofgroups = self.goals.get( loc, None)
        if listofgroups != None:
            [group.deleteDest() for group in listofgroups]
            del self.goals[loc]

    # updates out map with any new walls that our ants have seen.
    def mergeMap(self,ants):
        for row in range(len(ants.map)):
            for col in range(len(ants.map[0])):
                if ants.map[row][col] == WATER: self.map[row][col] = WATER


        
# =========================== DEPRECIATED PATH FINDING ALGORITHMS================================       
    # BFS LIKE A BOSS SEARCH
    # instead of a single goal, if the group sees a piece
    # of food before it gets to its actual goal the search
    # stops and returns that piece of food. This method
    # is depreciated due to length of runtime. Astar below
    # is the food finding implementation
    
    def breadthFirstSearch(self, start, goals, ants):
        distance = min([ants.distance(start, food) for food in goals])
##        if distance >= 10:
##            raise
        for goal in goals:
            if goal == start: return None
        
        visited = [start]
        queue = [(start[0], start[1], [])]
      
        while len(queue) > 0:
            position = queue.pop(0)
            for goal in goals:
                if (goal[0], goal[1]) == (position[0], position[1]): return position

            for new in [(position[0] - 1, position[1], ["n"]), (position[0] + 1, position[1], ["s"]), \
                        (position[0], position[1] - 1, ["w"]), (position[0], position[1] + 1, ["e"])]:
                newX,newY = new[0] % ants.rows, new[1] % ants.cols
                if ((newX,newY) not in visited) and (self.map[newX][newY] != WATER) \
                                                and (self.map[newX][newY] != "M"):
                    visited.append( (newX, newY) )
                    queue.append( (newX, newY, position[2] + new[2]))

        # for finding no path because derp
        return None

    # this is used to move two ants into formation 
    def directed(self, location1, location2, ants):
        if location1 == location2: return []
        
        locs = {}
        swap = True
        
        visitedOne = [location1]
        queueOne = [location1 + ([],)]
        
        visitedTwo = [location2]
        queueTwo = [location2 + ([],)]

        while True:
            if swap and len(queueOne) > 0:
                position = queueOne.pop(0)
                possiblePath = locs.get( (position[0], position[1]), None)
                if possiblePath != None: return position[0], position[1], position[2] + [BEHIND[vec] for vec in possiblePath]
                else: locs[ (position[0], position[1]) ] = position[2]
                for new in [(position[0] - 1, position[1], ["n"]), (position[0] + 1, position[1], ["s"]), \
                        (position[0], position[1] - 1, ["w"]), (position[0], position[1] + 1, ["e"])]:
                    newX,newY = new[0] % ants.rows, new[1] % ants.cols
                    if ((newX,newY) not in visitedOne) and (self.map[newX][newY] != WATER) \
                                    and (self.map[newX][newY] != "M"):
                        
                        visitedOne.append( (newX, newY) )
                        dist = ants.distance( (newX, newY), location2)
                        queueOne.append( (newX, newY, position[2] + new[2]) )

                
            elif not swap and len(queueTwo) > 0:
                position = queueTwo.pop(0)
                possiblePath = locs.get( (position[0], position[1]), None)
                if possiblePath != None: return position[0], position[1], possiblePath + [BEHIND[vec] for vec in position[2]]
                else: locs[ (position[0], position[1]) ] = position[2]
                for new in [(position[0] - 1, position[1], ["n"]), (position[0] + 1, position[1], ["s"]), \
                        (position[0], position[1] - 1, ["w"]), (position[0], position[1] + 1, ["e"])]:
                    newX,newY = new[0] % ants.rows, new[1] % ants.cols
                    if ((newX,newY) not in visitedTwo) and (self.map[newX][newY] != WATER) \
                                    and (self.map[newX][newY] != "M"):
                        newX,newY = new[0] % ants.rows, new[1] % ants.cols
                        visitedTwo.append( (newX, newY) )
                        dist = ants.distance( (newX, newY), location2)
                        queueTwo.append ((newX, newY, position[2] + new[2]))
            elif len(queueOne) == 0 and len(queueTwo) == 0: return None
            swap = not swap

#==================PATHFINDING ALGORITHMS USED==============

    def directedAStar(self, location1, location2, ants):
        if location1 == location2: return []
        
        locs = {}
        swap = True
        
        visitedOne = [location1]
        queueOne = util.PriorityQueue()
        queueOne.push(location1 + ([],), 0)
        
        visitedTwo = [location2]
        queueTwo = util.PriorityQueue()
        queueTwo.push(location2 + ([],), 0)

        while True:
            if swap and not queueOne.isEmpty():
                position = queueOne.pop()
                possiblePath = locs.get( (position[0], position[1]), None)
                if possiblePath != None: return position[0], position[1], position[2] + [BEHIND[vec] for vec in possiblePath]
                else: locs[ (position[0], position[1]) ] = position[2]
                for new in [(position[0] - 1, position[1], ["n"]), (position[0] + 1, position[1], ["s"]), \
                        (position[0], position[1] - 1, ["w"]), (position[0], position[1] + 1, ["e"])]:
                    newX,newY = new[0] % ants.rows, new[1] % ants.cols
                    if ((newX,newY) not in visitedOne) and (self.map[newX][newY] != WATER) \
                                    and (self.map[newX][newY] != "M"):
                        
                        visitedOne.append( (newX, newY) )
                        dist = ants.distance( (newX, newY), location2)
                        queueOne.push( (newX, newY, position[2] + new[2]), len(position[2]) + 1 + dist )

                
            elif not swap and not queueTwo.isEmpty():
                position = queueTwo.pop()
                possiblePath = locs.get( (position[0], position[1]), None)
                if possiblePath != None: return position[0], position[1], possiblePath + [BEHIND[vec] for vec in position[2]]
                else: locs[ (position[0], position[1]) ] = position[2]
                for new in [(position[0] - 1, position[1], ["n"]), (position[0] + 1, position[1], ["s"]), \
                        (position[0], position[1] - 1, ["w"]), (position[0], position[1] + 1, ["e"])]:
                    newX,newY = new[0] % ants.rows, new[1] % ants.cols
                    if ((newX,newY) not in visitedTwo) and (self.map[newX][newY] != WATER) \
                                    and (self.map[newX][newY] != "M"):
                        newX,newY = new[0] % ants.rows, new[1] % ants.cols
                        visitedTwo.append( (newX, newY) )
                        dist = ants.distance( (newX, newY), location2)
                        queueTwo.push( (newX, newY, position[2] + new[2]), len(position[2]) + 1 + dist )
            elif queueOne.isEmpty() and queueTwo.isEmpty(): return None
            swap = not swap

    # astar pathfinding
    def aStar(self, start, goals, ants):

        distance, aGoal = min([(ants.distance(start, food), food) for food in goals])
        goals = goals[:]
        goals.remove(aGoal)
##        if distance >= 10:
##            raise
        
        for goal in goals:
            if start == goal: return []

        visited = [start]
        queue = util.PriorityQueue()
        queue.push(start + ([],), 0)

        while not queue.isEmpty():
            position = queue.pop()
            if (position[0], position[1]) == aGoal: return position
            for goal in goals:
                if (position[0], position[1]) == goal: return position
            for new in [(position[0] - 1, position[1], ["n"]), (position[0] + 1, position[1], ["s"]), \
                        (position[0], position[1] - 1, ["w"]), (position[0], position[1] + 1, ["e"])]:
                    newX,newY = new[0] % ants.rows, new[1] % ants.cols
                    if ((newX,newY) not in visited) and (self.map[newX][newY] != WATER) \
                                    and (self.map[newX][newY] != "M"):
                        visited.append( (newX, newY) )
                        queue.push( (newX, newY, position[2] + new[2]), len(position[2]) + 1 + ants.distance( (newX, newY), aGoal) )
        
    # returns a pretty representation of a map
    def render_text_map(self,ants):
        'return a pretty string representing the map'
        tmp = ''
        for row in self.map:
            tmp += '# %s\n' % ''.join([MAP_RENDER[col] for col in row])
        return tmp
    
class AntGroup(object):
    
    def __init__(self, antInfo, sim, bot):
        self.sim = sim
        self.location = [-1, -1]
        self.path = []
        self.destination = None
        self.members = antInfo
        self.vector = util.Counter()
        self.bot = bot

    # if the group is empty because there are no
    # more ants, remove it from the bots groups
    # list and then delete yourself
    def removeAnt(self, loc, name):
        self.members.remove(loc)
        if len(self) > 0:
            self.updateLocation()
        else:
            groups = self.bot.groups[name].get(self.location, None)
            if groups != None and self in groups: groups.remove(self)
            goals = self.bot.goals.get(self.destination, None)
            if goals != None and self in goals: goals.remove(self)
                
                
    
    def addAnt(self, loc):
        if loc not in self.members:
            self.members.append(loc)
            self.updateLocation()

    # for psuedo random movement
    # this removes the backwards
    # movement from the possibilites and
    # gives the forward motion a 75%
    # to be chosen again by default
    def resetProb(self, vec, prob = 0.75):
        self.vector = util.Counter()
        direct = ["n", "e", "s", "w"]
        self.vector[vec] = prob
        direct.remove(vec)
        direct.remove(BEHIND[vec])
        for d in direct:
            self.vector[d] = (1 - prob) / 2.0

    def __len__(self): return len(self.members)

    # update the group loc with the new leader
    def updateLocation(self):
        
        self.location = self.members[0]


    def contains(self, loc):
        for ant in self.members:
            if ant == loc:
                return True
        return False

    # a simple averaging of x any ys
    def calculateCenter(self):
        x,y,size = 0,0,len(self.members)
        for mem in self.members:
            x += mem[0]
            y += mem[1]
        return [x/size, y/size]

    def deleteDest(self): self.destination = None
        
class Explorer(AntGroup):
    def __init__(self,antInfo, sim, bot):
        AntGroup.__init__(self, antInfo, sim, bot)
        directions = ["n", "e", "w", "s"]
        direction = random.choice(directions)
        self.resetProb(direction)
        self.formation = True
        self.degree = 1
        
        

    def move(self, foods):


        self.temp = []
        # the formation logic, uses a directed
        # a star graph search to find the correct
        # path from the leader to the new ant
        if not self.formation and len(self) > 1:
            if self.destination != None:
                self.path = []
                self.destination = None
            if self.path == []:
                debug("CALLED DIRECTED ASTAR","LOC_1", self.members[0], "LOC_2", self.members[1])
                time.clock()
                x,y,self.path = self.bot.directedAStar(self.members[0], self.members[1], self.sim)
                elapsed = time.clock()
                debug("ENDED DIRECTED ASTAR", "time", elapsed, "path", self.path)
            

        # if we have a formation, but do not have a destination, generate a
        # destination/path
        elif self.destination == None:
            try:
                debug("CALLED A* SEARCH", "LOC", self.location, "GOALS", foods)
                time.clock()
                x,y,self.path = self.bot.aStar(self.location, foods, self.sim)
                elapsed = time.clock()
                debug("ENDED A*", "time", elapsed, "destination", (x,y), "path", self.path)
                self.destination = (x,y)

                # updates the bos with the goal for this group
                test = self.bot.goals.get( (self.destination[0], self.destination[1]), None)
                if test == None:
                    self.bot.goals[ (self.destination[0], self.destination[1]) ] = [self]
                else:
                    self.bot.goals[ (self.destination[0], self.destination[1]) ].append(self)

            # if the aStar fails because how far away the closest food is
            except:
                self.path = [util.sample(self.vector)]
                self.resetProb(self.path[0])

        # leader ant movement
        leader = self.members[0]
        vec = self.path[0]
        new_loc = self.sim.destination(leader, vec)
        old_loc = leader

        # if the location is valid, move to it
        group = self.bot.antLocs.get(new_loc, None)
        if self.sim.passable(new_loc) and group == None:

            self.moveSingleAnt(0, vec, new_loc)
            self.path.pop(0)
            if self.destination != None and self.sim.distance(new_loc, self.destination) <= 1:
                self.bot.deleteGoals(self.destination)
                self.destination = None
                self.path = []

        elif self.sim.passable(new_loc) and group == self:
            self.members[0] = new_loc
            self.sim.issue_order( (leader, vec) )
            self.temp.append(vec)
            

        # if invalid, move out of the way, leader and subordinate shift
        # either left, right, or stay still
        else:
            probs = util.Counter()
            for vect in SIDES[vec]:
                probs[vect] = 1.0
            probs.normalize()
            for i in range(len(probs)):
                vect = util.sample(probs)
                new_loc = self.sim.destination(leader, vect)
                new_loc_2 = self.sim.destination(self.members[-1], vect)
                if self.sim.passable(new_loc) and self.bot.antLocs.get(new_loc, None) == None \
                   and self.sim.passable(new_loc_2) and self.bot.antLocs.get(new_loc_2, None) == None:
                    if self.members[-1] != leader:
                        self.moveSingleAnt(-1, vect, new_loc)
                    self.moveSingleAnt(0, vect, new_loc)
                    self.path.insert(0, BEHIND[vect])
                    self.updateLocation()
                    return    
                probs.pop(vect)
            return

        # for the subordinant ants, follow the leader!
        for mem in self.members[1:]:
            if self.formation:
                vec = self.sim.direction(mem, old_loc)[0]
                
                debug("sub vec", vec)
            else:
                vec = BEHIND[self.path[-1]]
            new_loc = self.sim.destination(mem, vec)
            debug("sub new_loc", new_loc)
            old_loc = mem
            debug("DISTANCE BETWEEN ANTS:", self.sim.distance(mem, leader))
            group = self.bot.antLocs.get(new_loc, None)
            if group == None:
                if not self.formation: self.path.pop(-1)
                self.moveSingleAnt(-1, vec, new_loc)
            elif self.formation and group == self:
                self.members[-1] = new_loc
                self.sim.issue_order( (mem, vec) )
                self.temp.append(vec)
            elif not self.formation and self.sim.distance(mem, self.members[0]) > 1:
                probs = util.Counter()
                for vect in SIDES[vec]:
                    probs[vect] = 1.0
                probs.normalize()
                for i in range(len(probs)):
                    vect = util.sample(probs)
                    new_loc = self.sim.destination(mem, vect)
                    if self.sim.unoccupied(new_loc) and self.bot.antLocs.get(new_loc, None) == None:
                        self.moveSingleAnt(-1, vect, new_loc)
                        self.path.append(BEHIND[vect])
                        break  
                    probs.pop(vect)
                
                

        # check to see if formation was achieved
        if not self.formation and self.sim.distance(self.members[0], self.members[1]) <= 1:
            self.formation = True
            self.path = []
                             
        self.updateLocation()
        debug("members:", self.members,"location", self.location, "formation flag:", self.formation, "destination:", self.destination if self.destination != None else "None", "PATH:", self.path, "Moves:", self.temp)

    # Updates both the group and bots backend, and then issues the actual move order
    def moveSingleAnt(self, index, vec, new_loc):
        mem = self.members[index]
        self.members[index] = new_loc
        self.bot.antLocs[new_loc] = self.bot.antLocs.pop(mem)
        self.sim.issue_order( (mem, vec) )
        self.temp.append(vec)
    
    def addAnt(self, loc):
        AntGroup.addAnt(self, loc)
        if len(self.members) > 1 and self.sim.distance(self.members[0], self.members[1]) > self.degree:
            self.formation = False

    # calls the super classes remove Ant with the correct classification
    def removeAnt(self, loc):
        if self.members.index(loc) == 0:
            self.destination = None
            self.path = []
        AntGroup.removeAnt(self, loc, "Explorer")
        

class Buster(AntGroup):
    pass

class Hunter(AntGroup):
    pass

    








 
            
if __name__ == '__main__':
    # psyco will speed up python a little, but is not needed
    try:
        import psyco
        psyco.full()
    except ImportError:
        pass
    
    try:
        # if run is passed a class with a do_turn method, it will do the work
        # this is not needed, in which case you will need to write your own
        # parsing function and your own game state class
        Ants.run(MyBot())
    except KeyboardInterrupt:
        print('ctrl-c, leaving ...')


##    # THE FOLLOWING WAS FOR USE IN TESTING SEARCH EFFICIENCIES.
##    vecs = {"e": (0, 1), "w": (0, -1), "n": (-1, 0), "s": (1, 0) }
##    bot = MyBot()
##    class lol:
##        def __init__(self, row, col):
##            self.map = []
##            for i in range(row):
##                l = []
##                for j in range(col):
##                    l.append(".")
##                self.map.append(l)
##            self.rows = row
##            self.cols = col
##        def distance(self, loc1, loc2):
##            'calculate the closest distance between to locations'
##            row1, col1 = loc1
##            row2, col2 = loc2
##            d_col = min(abs(col1 - col2), self.cols - abs(col1 - col2))
##            d_row = min(abs(row1 - row2), self.rows - abs(row1 - row2))
##            return d_row + d_col
##
##    ants = lol(100, 100)
##    bot.map = ants.map
##    start = (0,0)
##    goal = (50 ,50)
##    for row in bot.map:
##        row[1] = WATER
##        row[-1] = WATER
##    bot.map[-2][1] = "."
##    bot.map[-1][0] = WATER
##    time.clock()
##    
##    path2 = bot.breadthFirstSearch(start, [goal], ants)
##    bfsTime = time.clock()
##    print "bfs   runtime      \t", bfsTime
##    
##    path3 = bot.directed(start, goal, ants)
##    directedBFS = time.clock()
##    print "directedbfs runtime\t", directedBFS
##
##    lol = bot.aStar( start, [goal], ants)
##    aStarTime = time.clock()
##    print "astar runtime      \t", aStarTime
##    
##    path = bot.directedAStar( start, goal, ants)
##    directedAStar = time.clock()
##    print "directedA* runtime \t", directedAStar
##    
##
##    
##
##    print "directed\t", path
##    print "astar\t\t", path2
##    def printMap(maps):
##        for row in maps:
##            print row
##        print "\n"
##    bot.map[start[0]][start[1]] = "A"
##    bot.map[goal[0]][goal[1]] = "G"
##    
##    map1 = bot.map[:]
##    map2 = bot.map[:]
##    #ASTAR PRINTINg
##    printMap(map1)
##    for vec in path2[2]:
##        tup = vecs[vec]
##        index = 0
##        
##        
##        col = max([row.index("A") for row in map1 if "A" in row])
##        row = max([index for index in range(len(map1)) if "A" in map1[index]])
##        
##        newX, newY = row + tup[0], col + tup[1]
##        map1[newX][newY] = "A"
##        map1[row][col] = "."
##        print vec
##        printMap(map1)
##
##    printMap(map2)
##    for rIndex in range(len(path[2])):
##        lIndex = -1 - rIndex
##
##        rVec = path[2][rIndex]
##        tup = vecs[rVec]
##        col = max([row.index("A") for row in map2 if "A" in row])
##        row = max([index for index in range(len(map2)) if "A" in map2[index]])
##        newX, newY = row + tup[0], col + tup[1]
##        if map2[newX][newY] == "G":
##            print rVec, lVec
##            printMap(map2)
##            break
##        map2[newX][newY] = "A"
##        map2[row][col] = "."
##
##        lVec = path[2][lIndex]
##        tup = vecs[lVec]
##        col = max([row.index("G") for row in map2 if "G" in row])
##        row = max([index for index in range(len(map2)) if "G" in map2[index]])
##        newX, newY = row + tup[0], col + tup[1]
##        if map2[newX][newY] == "A":
##            print rVec, lVec
##            printMap(map2)
##            break
##        map2[newX][newY] = "G"
##        map2[row][col] = "."
##
##        print rVec, lVec
##        printMap(map2)
    
    
        
